package com.itcam.phaselist.list_;

/**
 * LinkedList底层结构
 * <p>
 * 说明：<p>
 * 1.LinkedList底层实现了双向链表和双端队列特点<p>
 * 2.可以添加任意元素（元素可以重复），包括null<p>
 * 3.线程不安全，没有实现同步<p>
 * <p>
 * 底层操作机制：<p>
 * 1.LinkedList底层维护了一个双向链表<p>
 * 2.LinkedList中维护了两个属性first和last分别指向首节点和尾节点<p>
 * 3.每个节点（Node对象），里面又维护了prev、next、item三个属性，其中通过prev指向前一个，通过next指向后一个，最终实现双向链表<p>
 */

public class LinkedList_ {
    public static void main(String[] args) {
        // 模拟一个简单的双向链表
        Node cammy = new Node("cammy");
        Node jerry = new Node("jerry");
        Node timi = new Node("timi");

        // 连接三个结点，形成双向链表
        // cammy -> jerry -> timi
        cammy.next = jerry;
        jerry.next = timi;

        // cammy <-- jerry <-- timi
        timi.pre = jerry;
        jerry.pre = cammy;

        Node first = cammy; // 让first引用指向jack,就是双向链表的头结点
        Node last = timi; // 让last引用指向hsp,就是双向链表的尾结点

        // 演示，从头到尾进行遍历
        System.out.println("===从头到尾进行遍历===");
        while (true) {
            if (first == null) {
                break;
            }
            // 输出first信息
            System.out.println(first);
            first = first.next;
        }

        // 演示，从尾到头进行遍历
        System.out.println("====从尾到头的遍历====");
        while (true) {
            if (last == null) {
                break;
            }
            // 输出last信息
            System.out.println(last);
            last = last.pre;
        }

        // 演示链表的添加对象
        // 在cammy --------- jerry之间插入一个对象smith
        // 先创建一个Node结点，name就是smith
        Node smith = new Node("smith");
        smith.next = jerry;
        smith.pre = cammy;
        jerry.pre = smith;
        cammy.next = smith;

        // 让first再次指向cammy
        first = cammy;
        System.out.println("===从头到尾进行遍历===");
        while (true) {
            if (first == null) {
                break;
            }
            // 输出first信息
            System.out.println(first);
            first = first.next;
        }

        // 让last再次指向timi
        last = timi;
        System.out.println("====从尾到头的遍历====");
        while (true) {
            if (last == null) {
                break;
            }
            // 输出last信息
            System.out.println(last);
            last = last.pre;
        }


    }
}

//定义一个Node类，Node对象表示双向链表的一个结点
class Node {
    public Object item; //真正存放数据
    public Node next; //指向后一个结点
    public Node pre; //指向前一个结点

    public Node(Object name) {
        this.item = name;
    }

    public String toString() {
        return "Node name = " + item;
    }
}
